/*
 *
 * Copyright (C) 2012 Walter Lütgenau
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * 
 */
package offset.nodes.server.model.security;

import java.security.Principal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Stack;
import java.util.logging.Level;
import java.util.logging.Logger;
import javax.jcr.observation.EventIterator;
import org.apache.jackrabbit.api.jsr283.security.AccessControlPolicy;
import org.apache.jackrabbit.api.jsr283.security.Privilege;
import org.apache.jackrabbit.core.HierarchyManager;
import org.apache.jackrabbit.core.ItemId;
import org.apache.jackrabbit.core.security.AMContext;
import org.apache.jackrabbit.core.security.AbstractAccessControlManager;
import org.apache.jackrabbit.core.security.AccessManager;
import org.apache.jackrabbit.core.security.AnonymousPrincipal;
import org.apache.jackrabbit.core.security.SystemPrincipal;
import org.apache.jackrabbit.core.security.authorization.AccessControlProvider;
import org.apache.jackrabbit.core.security.authorization.NamedAccessControlPolicyImpl;
import org.apache.jackrabbit.core.security.authorization.PrivilegeRegistry;
import org.apache.jackrabbit.core.security.authorization.WorkspaceAccessManager;
import org.apache.jackrabbit.spi.Name;
import org.apache.jackrabbit.spi.Path;
import org.apache.jackrabbit.spi.commons.conversion.NamePathResolver;

import javax.jcr.AccessDeniedException;
import javax.jcr.Item;
import javax.jcr.Node;
import javax.jcr.NodeIterator;
import javax.jcr.PathNotFoundException;
import javax.jcr.RepositoryException;
import javax.jcr.Session;
import javax.jcr.Value;
import javax.jcr.observation.Event;
import javax.jcr.observation.EventListener;
import javax.security.auth.Subject;
import offset.nodes.Constants;
import offset.nodes.client.model.SimpleNamespaceRegistry;
import offset.nodes.client.virtual.model.jcr.QName;
import offset.nodes.server.model.RepositoryStartupExtension;
import offset.nodes.server.model.XPathQuery;
import offset.nodes.server.search.model.DistinctNodeIterator;
import org.apache.jackrabbit.core.security.authorization.Permission;
import org.apache.jackrabbit.spi.Path.Element;
import org.apache.jackrabbit.spi.commons.name.NameFactoryImpl;
import org.apache.jackrabbit.spi.commons.name.PathFactoryImpl;

/**
 * <code>SimpleAccessManager</code> ...
 */
public class PathAccessManager extends AbstractAccessControlManager implements AccessManager {

    /**
     * The policy returned upon {@link #getEffectivePolicies(String)}
     */
    private static final AccessControlPolicy POLICY = new NamedAccessControlPolicyImpl("Simple AccessControlPolicy");
    /**
     * Subject whose access rights this AccessManager should reflect
     */
    private AMContext context;

    private WorkspaceAccessManager wspAccessMgr;
    private PrivilegeRegistry privilegeRegistry;
    Session systemSession;
    private boolean initialized;
    private boolean system;
    private boolean anonymous;
    HashMap<Integer, ACNode> permissionRoots = new HashMap<Integer, ACNode>();
    PermissionsCache permissionsCache = new PermissionsCache();
    UserNodePrincipal user;
    Node[] roles;
    CondensedACE[] accessControlEntries;
    static PathAccessManager instance = null;

    /**
     * Empty constructor
     */
    public PathAccessManager() {
        initialized = false;
        anonymous = false;
        system = false;
    }

    //------------------------------------------------------< AccessManager >---
    /**
     * {@inheritDoc}
     */
    public void init(AMContext context)
            throws AccessDeniedException, Exception {
        init(context, null, null);
    }

    class CondensedACE {

        SimpleNamespaceRegistry namespaces = SimpleNamespaceRegistry.getInstance();
        public int permission;
        public boolean granted;
        public Path path;

        public CondensedACE(int permission, boolean granted, String pathString) {
            this.permission = permission;
            this.granted = granted;
            this.path = toPath(pathString);
        }

        public boolean isGranted() {
            return granted;
        }

        public void setGranted(boolean granted) {
            this.granted = granted;
        }

        public Path getPath() {
            return path;
        }

        public String getManagedNodePathString() throws IllegalArgumentException, RepositoryException {
            return getPathString(path);
        }

        protected String getPathString(Path path) {
            StringBuffer buf = new StringBuffer();
            for (int i = 0; i < path.getElements().length; i++) {
                Element element = path.getElements()[i];

                if (i > 0)
                    buf.append("/");
                buf.append(namespaces.toPrefixName(new QName(element.getName().getNamespaceURI(), element.getName().getLocalName())));
                if (element.getIndex() > 0)
                    buf.append("[" + element.getIndex() + "]");
            }

            return buf.toString();
        }

        public int getPermission() {
            return permission;
        }

        protected Path toPath(String pathString) {
            String[] pathComponents = pathString.split("/");
            Element[] elements = new Element[pathComponents.length];

            for (int i = 0; i < pathComponents.length; i++) {
                String pathComponent = pathComponents[i];

                int index = -1;
                String namespaceURI = "";
                String localName;

                if (pathComponent.indexOf("[") > 0) {
                    int start = pathComponent.indexOf("[");
                    int end = pathComponent.indexOf("]");

                    index = Integer.valueOf(pathComponent.substring(start + 1, end)).intValue();
                    pathComponent = pathComponent.substring(0, start);
                }

                if (pathComponent.indexOf(":") > 0) {
                    String[] parts = pathComponent.split(":");

                    namespaceURI = namespaces.getURI(parts[0]);
                    localName = parts[1];
                } else
                    localName = pathComponent;



                Element element;
                if (index < 0)
                    element = PathFactoryImpl.getInstance().createElement(NameFactoryImpl.getInstance().create(namespaceURI, localName));
                else
                    element = PathFactoryImpl.getInstance().createElement(NameFactoryImpl.getInstance().create(namespaceURI, localName), index);

                elements[i] = element;
            }

            return PathFactoryImpl.getInstance().create(elements);
        }
    }

    /**
     * {@inheritDoc}
     */
    public void init(AMContext context, AccessControlProvider acProvider, WorkspaceAccessManager wspAccessManager) throws AccessDeniedException, Exception {
        if (initialized)
            throw new IllegalStateException("already initialized");

        this.context = context;
        this.privilegeRegistry = new PrivilegeRegistry(context.getNamePathResolver());
        this.wspAccessMgr = wspAccessManager;
        this.anonymous = !context.getSubject().getPrincipals(AnonymousPrincipal.class).isEmpty();
        this.system = !context.getSubject().getPrincipals(SystemPrincipal.class).isEmpty();
        this.systemSession = PasswordLoginModule.getSystemSession();

        // @todo check permission to access given workspace based on principals
        initialized = true;

        if (!canAccess(context.getWorkspaceName()))
            throw new AccessDeniedException("Not allowed to access Workspace " + context.getWorkspaceName());

        Principal principal = (Principal) context.getSubject().getPrincipals().toArray()[0];
        if (!(principal instanceof UserNodePrincipal))
            return;
        user = (UserNodePrincipal) principal;

        initAccessControl();
        new PathAccessManagerStartupExtension().onStartup(systemSession);
    }

    /**
     * Invalidate all permission caches for the user
     * 
     * @throws RepositoryException
     */
    protected void invalidate() throws RepositoryException {
        permissionRoots = new HashMap<Integer, ACNode>();
        permissionsCache = new PermissionsCache();
        initAccessControl();
    }

    /**
     * Initialize the access control caches. Read all nodes of the user, condense multiple nodes of the same path to a single
     * effective access control node and setup up the privilege tree.
     *
     * @throws RepositoryException
     */
    protected void initAccessControl() throws RepositoryException {
        roles = readAllRolesOfUser(user);
        Node[] aceNodes = readACENodes(roles, user);
        accessControlEntries = condenseACENodes(aceNodes);
        for (CondensedACE ace : accessControlEntries) {
            ACNode root = getPermissionRoot(ace.getPermission());
            root.addNode(ace.getPath(), ace.isGranted());
        }

    }

    /**
     * Add and implement observer for modification of roles and access control entries
     */
    class PathAccessManagerStartupExtension implements RepositoryStartupExtension, EventListener {

        /**
         * Add observer for roles and access control entries
         *
         * @param systemSession The system session used to do the work
         */
        public void onStartup(Session session) {
            try {
                session.getWorkspace().getObservationManager().addEventListener(
                        this,
                        Event.NODE_ADDED + Event.NODE_REMOVED + Event.PROPERTY_ADDED + Event.PROPERTY_CHANGED + Event.PROPERTY_REMOVED,
                        "/",
                        true,
                        null,
                        new String[]{Constants.TYPENAME_ACCESS_CONTROL_ENTRY, Constants.TYPENAME_ROLE},
                        true);
            } catch (RepositoryException ex) {
                Logger.getLogger(PathAccessManager.class.getName()).log(Level.SEVERE, null, ex);
            }
        }

        /**
         * When receiving an event, check, if a role or an access control entry is affected. If necessary, restart AC initialization
         *
         * @param events The events received
         */
        public void onEvent(EventIterator events) {
            try {
                boolean invalidate = false;
                HashSet<String> processedPathes = new HashSet<String>();

                while (!invalidate && events.hasNext()) {
                    Event event = events.nextEvent();
                    if (event.getType() == Event.NODE_REMOVED || event.getType() == Event.PROPERTY_REMOVED) {
                        // too difficult to optimize this. Invalidate anyway
                        invalidate = true;
                        break;
                    }

                    Node node;
                    Item item = systemSession.getItem(event.getPath());

                    if (item.isNode())
                        node = (Node) item;
                    else
                        node = item.getParent();

                    if (node.isNodeType(Constants.TYPENAME_ACCESS_CONTROL_ENTRY)) {
                        invalidate = accessControlEntryChanged(event, node);
                        processedPathes.add(node.getPath());
                    } else if (node.isNodeType(Constants.TYPENAME_ROLE)) {
                        invalidate = true;
                        processedPathes.add(node.getPath());
                    }
                }

                if (invalidate)
                    invalidate();
            } catch (RepositoryException ex) {
                Logger.getLogger(PathAccessManager.class.getName()).log(Level.SEVERE, null, ex);
            }

        }

        /**
         * An access control entry has been modified. There are two possibilites, how the current user could have been affected:
         * 1. A role of the current user could have been removed from an ACE
         * 2. A role of the current user could have been added to an ACE
         *
         * @param event
         * @param node
         * @return
         * @throws RepositoryException
         */
        protected boolean accessControlEntryChanged(Event event, Node node) throws RepositoryException {
            // check, if a role of the current user has been removed from one of its ACEs. We simply test, if an ACE of the user has been modified at all.
            for (int i = 0; i < accessControlEntries.length; i++) {
                String acePath = accessControlEntries[i].getManagedNodePathString();
                if (acePath.equals(event.getPath()))
                    return true;
            }

            // check, if a role of the current user has been added to some ACE entry
            String uuid = null;
            NodeIterator it = node.getNodes();
            while (it.hasNext()) {
                Node child = it.nextNode();

                if (!child.getName().equals(Constants.TYPENAME_PRIVILEGES)) {
                    uuid = child.getProperty(Constants.PROP_REFERENCE).getString();
                    break;
                }
            }

            for (int i = 0; i < roles.length; i++) {
                if (roles[i].getUUID().equals(uuid))
                    return true;
            }

            if (user.getUser().getUUID().equals(uuid))
                return true;

            return false;
        }
    }

    /**
     * Read all roles of a given user and return them as an array
     * 
     * @param user The user
     * @return The array of Node objects representing the roles
     * @throws javax.jcr.RepositoryException
     */
    protected Node[] readAllRolesOfUser(UserNodePrincipal user) throws RepositoryException {
        XPathQuery query = new XPathQuery(systemSession);
        NodeIterator ni = query.executeQuery(
                "/jcr:root//element(*, " + Constants.TYPENAME_ROLE + ")[@" + Constants.PROP_USER_REFERENCE + "='" + user.getUser().getUUID() + "']");
        ni = new DistinctNodeIterator(ni);

        Node[] result = new Node[(int) ni.getSize()];
        for (int i = 0; ni.hasNext(); i++) {
            result[i] = ni.nextNode();
        }

        return result;
    }

    /**
     * Read all access control entries, that refer to one of the roles passed as an argument or to the principal passed as an argument.
     *
     * @param roles The nodes representing the roles
     * @param user The user
     * @return The access control entries, represented as Node objects
     * @throws javax.jcr.RepositoryException
     */
    protected Node[] readACENodes(Node[] roles, UserNodePrincipal user) throws RepositoryException {
        XPathQuery query = new XPathQuery(systemSession);
        StringBuffer queryString = new StringBuffer("/jcr:root//" + Constants.TYPENAME_ACCESS_CONTROL_ENTRY + "/element(*, " + Constants.TYPENAME_PRINCIPAL + ")[" +
                "@" + Constants.PROP_REFERENCE + "='" + user.getUser().getUUID() + "'");
        for (int i = 0; i <
                roles.length; i++) {
            queryString.append(" or @" + Constants.PROP_REFERENCE + "='" + roles[i].getUUID() + "'");
        }

        queryString.append("]");

        NodeIterator ni = query.executeQuery(queryString.toString());
        Node[] result = new Node[(int) ni.getSize()];
        for (int i = 0; ni.hasNext(); i++) {
            result[i] = ni.nextNode().getParent();
        }

        return result;
    }
    /**
     * Maps privilege strings to permission integers.
     */
    static HashMap<String, Integer> permissionMappings = new HashMap<String, Integer>();

    static {
        permissionMappings.put(Constants.PRIVILEGE_READ, new Integer(Permission.READ));
        permissionMappings.put(Constants.PRIVILEGE_ADD_NODE, new Integer(Permission.ADD_NODE));
        permissionMappings.put(Constants.PRIVILEGE_REMOVE_NODE, new Integer(Permission.REMOVE_NODE));
        permissionMappings.put(Constants.PRIVILEGE_SET_PROPERTY, new Integer(Permission.SET_PROPERTY));
        permissionMappings.put(Constants.PRIVILEGE_REMOVE_PROPERTY, new Integer(Permission.REMOVE_PROPERTY));
    }

    /**
     * Condense access control entries, i.e. combine multiple access control entries referring to the same privilege and having
     * the same path to a single entry.
     *
     * For that, first sort the access control entry according to their path. Doing that, access control entries of the same parent will be sorted according to their name.
     * This is essential for the priority of privileges within a given access control list.
     *
     * For example, imagine we have a role "all" and a role "admin" and a given user has both roles.
     * If the "Read" privilege for "all" is "denied" and for "admin" is "granted", the sequence admin -> all will deny the privilege for the user, whereas the sequence
     * all -> admin will grant the privilege to the user and only deny it for other members of the role "all".
     *
     * @param acNodes Node objects representing access control entries
     * @return an array of condensed access control entries
     * @throws javax.jcr.RepositoryException
     */
    protected CondensedACE[] condenseACENodes(Node[] aceNodes) throws RepositoryException {
        Arrays.sort(aceNodes, new Comparator() {

            public int compare(Object o1, Object o2) {
                try {
                    Node n1 = (Node) o1;
                    Node n2 = (Node) o2;

                    // if this is the same managed node, the order of the access control entries is important
                    if (n1.getParent().getParent().getPath().equals(n2.getParent().getParent().getPath()))
                        return n1.getPath().compareTo(n2.getPath());

                   String[] path1 = n1.getParent().getParent().getPath().split("/");
                   String[] path2 = n2.getParent().getParent().getPath().split("/");

                   int commonLength = Math.min(path1.length, path2.length);

                   for (int i=0; i<commonLength; i++) {
                       int compare = path1[i].compareTo(path2[i]);
                       if (compare != 0)
                           return compare;
                   }

                   return path1.length - path2.length;
                } catch (RepositoryException ex) {
                    Logger.getLogger(PathAccessManager.class.getName()).log(Level.SEVERE, null, ex);
                    return 0;
                }
            }
        });

        HashMap<Integer, ArrayList<CondensedACE>> condensedACEs = new HashMap<Integer, ArrayList<CondensedACE>>();

        int condensedCount = 0;
        HashMap<Integer, Stack<CondensedACE>> aceStacks = new HashMap<Integer, Stack<CondensedACE>>();
        for (int i = 0; i <
                aceNodes.length; i++) {
            Node aceNode = aceNodes[i];

            NodeIterator privileges = aceNode.getNode(Constants.TYPENAME_PRIVILEGES).getNodes();

            while (privileges.hasNext()) {
                Node privilege = privileges.nextNode();

                Integer permission = permissionMappings.get(privilege.getName());
                if (permission == null)
                    continue;

                Stack<CondensedACE> aceStack = aceStacks.get(permission);
                if (aceStack == null) {
                    aceStack = new Stack<CondensedACE>();
                    aceStacks.put(permission, aceStack);
                }
                String managedNodePath = aceNode.getParent().getParent().getPath();
                // remove all non parent entries from ace path
                while (aceStack.size() > 0 && !(managedNodePath+"/").startsWith(aceStack.peek().getManagedNodePathString()+"/")) {
                    aceStack.pop();
                }

                boolean granted = privilege.getProperty(Constants.PROP_PRESENCE).getString().equals(Constants.VALUE_GRANTED);
                boolean isUserRole = isUserRole(aceNode);

                if (!granted && !isUserRole) // explicitly denied, but for others. No effect for this user
                    continue;
                if (granted && !isUserRole) // explicitly granted, but only for other users. This user is denied.
                    granted = false;
                if (aceStack.size() > 0 && aceStack.peek().isGranted() == granted) // nothing changes, forget entry
                    continue;

                CondensedACE condensedACE = null;
                ArrayList<CondensedACE> condensedACEsPerPermission = condensedACEs.get(permission);
                if (aceStack.size() > 0 && aceStack.peek().getManagedNodePathString().equals(managedNodePath))
                    condensedACE = aceStack.peek();

                if (condensedACE == null) {
                    if (condensedACEsPerPermission == null) {
                        condensedACEsPerPermission = new ArrayList<CondensedACE>();
                        condensedACEs.put(permission, condensedACEsPerPermission);
                    }

                    condensedACE =
                            new CondensedACE(permission.intValue(), granted, managedNodePath);
                    condensedACEsPerPermission.add(condensedACE);

                    condensedCount++;

                } else
                    condensedACE.setGranted(granted);

                aceStack.push(condensedACE);
            }

        }

        CondensedACE[] result = new CondensedACE[condensedCount];
        int i = 0;
        Iterator<ArrayList<CondensedACE>> cACEs = condensedACEs.values().iterator();
        while (cACEs.hasNext()) {
            Iterator<CondensedACE> cACE = cACEs.next().iterator();
            while (cACE.hasNext()) {
                result[i++] = cACE.next();
            }

        }

        return result;
    }

    public ACNode getPermissionRoot(
            int permission) throws RepositoryException {
        ACNode permissionRoot = permissionRoots.get(permission);
        if (permissionRoot == null) {
            // init root
            permissionRoot = new ACNode(PathFactoryImpl.getInstance().create("{}"), 0, new Boolean(true)); // per default, root has all permissions
            // store root in permissionRoots
            permissionRoots.put(new Integer(permission), permissionRoot);
        }

        return permissionRoot;

    }

    /**
     * {@inheritDoc}
     */
    public synchronized void close() throws Exception {
        checkInitialized();
        initialized =
                false;
    }

    /**
     * {@inheritDoc}
     */
    public void checkPermission(ItemId id, int permissions)
            throws AccessDeniedException, RepositoryException {
        if (!isGranted(id, permissions))
            throw new AccessDeniedException("Access denied");
    }

    class PermissionsCache {

        HashMap<Integer, HashMap<ItemId, Boolean>> caches = new HashMap<Integer, HashMap<ItemId, Boolean>>();

        public PermissionsCache() {
            caches.put(new Integer(READ), new HashMap<ItemId, Boolean>());
            caches.put(new Integer(WRITE), new HashMap<ItemId, Boolean>());
            caches.put(new Integer(REMOVE), new HashMap<ItemId, Boolean>());
        }

        /**
         * Check cache for permissions
         *
         * @param id
         * @param permissions
         * @return
         */
        public Boolean hasPermissions(ItemId id, int permissions) {
            int permission;
            Boolean hasPermission;

            Iterator<Integer> it = permissionMappings.values().iterator();
            while (it.hasNext()) {
                int permissionType = it.next().intValue();

                permission = permissions & permissionType;
                if (permission > 0) {
                    hasPermission = caches.get(new Integer(permissionType)).get(id);
                    if (hasPermission == null || hasPermission.booleanValue() == false)
                        return hasPermission;
                    if (permission == permissions) // no other permissions encoded
                        break;
                }
            }

            return new Boolean(true);
        }

        class CacheStorage {

            class CacheEntry {

                ItemId id;
                int permission;

                public CacheEntry(ItemId id, int permission) {
                    this.id = id;
                    this.permission = permission;
                }

                public ItemId getId() {
                    return id;
                }

                public int getPermission() {
                    return permission;
                }
            }
            public static final int MAX_CACHE = 500;
            CacheEntry[] entries = new CacheEntry[MAX_CACHE];
            int size = 0;
            int start = 0;
            int end = 0;

            protected void remove() {
                caches.get(entries[start].getPermission()).remove(entries[start].getId());
                start++;
                if (start >= MAX_CACHE)
                    start = 0;
                size--;
            }

            public void add(ItemId id, int permission) {
                if (size + 1 > MAX_CACHE)
                    remove();
                if (size > 0 && entries[start].getId().equals(id))
                    remove();

                entries[end++] = new CacheEntry(id, permission);
                if (end >= MAX_CACHE)
                    end = 0;
                size++;
            }
        }
        CacheStorage cacheStorage = new CacheStorage();

        public void addPermission(ItemId id, int permission, boolean granted) {
            cacheStorage.add(id, permission);
            caches.get(permission).put(id, new Boolean(granted));
        }
    }

    /**
     * {@inheritDoc}
     */
    public boolean isGranted(ItemId id, int permissions) throws RepositoryException {
        checkInitialized();

        // check cache
        Boolean hasPermissions = permissionsCache.hasPermissions(id, permissions);
        if (hasPermissions != null)
            return hasPermissions.booleanValue();

        // check path
        Path path = context.getHierarchyManager().getPath(id);
        return isGranted(id, path, permissions);
    }

    public boolean isGranted(Path parentPath, Name childName, int permissions) throws RepositoryException {
        return isGranted(parentPath, permissions);
    }

    public boolean canRead(Path itemPath) throws RepositoryException {
        return isGranted(itemPath, READ);
    }

    public boolean isGranted(Path absPath, int permissions) throws RepositoryException {
        return isGranted(null, absPath, permissions);
    }

    public boolean isGranted(ItemId id, Path absPath, int permissions) throws RepositoryException {
        if (!absPath.isAbsolute())
            throw new RepositoryException("Absolute path expected");
        checkInitialized();

        if (system)
            // system has always all permissions
            return true;

        Iterator<Integer> it = permissionMappings.values().iterator();
        while (it.hasNext()) {
            int permissionType = it.next().intValue();

            int permission = permissions & permissionType;
            if (permission > 0) {
                ACNode acNode = getPermissionRoot(permissionType);
                boolean granted =  permissionGranted(acNode, absPath);
                if (id != null)
                    permissionsCache.addPermission(id, permission, granted);
                if (!granted)
                    return false;
            }
        }

        return true;

    }

    /**
     * Determine, if a given access control entry is associated to one of the user's roles.
     *
     * @param aceNode The access control entry
     * @return True, if the access control entry is associated to the user, else false
     * @throws RepositoryException
     */
    protected boolean isUserRole(Node aceNode) throws RepositoryException {
        NodeIterator ni = aceNode.getNodes();

        // find role node
        Node found = null;
        while (ni.hasNext()) {
            Node node = ni.nextNode();

            if (!node.getName().equals(Constants.TYPENAME_PRIVILEGES)) {
                found = node;
                break;
            }
        }

        if (found == null) // should not happen
            return false;

        // determine role Id
        String roleId = found.getProperty(Constants.PROP_REFERENCE).getString();
        for (int i = 0; i < roles.length; i++) {
            if (roles[i].getUUID().equals(roleId))
                return true;
        }

        return false;
    }

    class ACNode {

        Boolean granted;
        int level;
        Path path;
        HashMap<Element, ACNode> children = new HashMap<Element, ACNode>();

        public ACNode(Path path, int level, Boolean granted) {
            this.path = path;
            this.granted = granted;
            this.level = level;
        }

        public void addNode(Path path, boolean granted) throws RepositoryException {
            if (path.equals(this.getPath())) {
                this.granted = new Boolean(granted);
                return;
            }

            ACNode node = this;
            ACNode found = null;
            while (node != null) {
                found = node.getChild(path);

                if (found == null) { // insert child into node
                    Path newPath = path.subPath(node.getLevel() + node.getPath().getLength(), path.getLength());
                    ACNode newNode = new ACNode(newPath,
                            node.getLevel() + node.getPath().getLength(), new Boolean(granted));
                    node.getChildren().put(newNode.getPath().getElements()[0], newNode);
                    return;
                }

                if (!found.subPathMatches(path)) // split node, see below
                    break;

                node = found;
            }

            // split found node
            // find first path element, that is different
            int commonLength = 0;
            for (int i = 0; i < path.getLength() - found.getLevel() && i < found.getPath().getLength(); i++) {
                if (!found.getPath().getElements()[i].equals(path.getElements()[i + found.getLevel()]))
                    break;
                commonLength = i + 1;
            }

            boolean newNodeIsAboveOldNode = false; // new ace path is above the node that has been found
            if (path.getLength() <= commonLength + found.getLevel())
                newNodeIsAboveOldNode = true;

            if (newNodeIsAboveOldNode) {
                ACNode oldNode = new ACNode(found.getPath().subPath(commonLength, found.getPath().getLength()),
                        found.getLevel()+commonLength, found.getGranted());
                oldNode.getChildren().putAll(found.getChildren());
                found.getChildren().clear();

                ACNode newNode = found;
                newNode.setGranted(granted);
                newNode.setPath(found.getPath().subPath(0, commonLength));

                newNode.getChildren().put(oldNode.getPath().getNameElement(), oldNode);
            } else {
                /*
                 * Split old node in common and old node part.
                 * Substitute found node with common node, add both new and old node below this common node
                 */
                ACNode oldNode = new ACNode(found.getPath().subPath(commonLength, found.getPath().getLength()),
                        found.getLevel() + commonLength, found.getGranted());
                oldNode.getChildren().putAll(found.getChildren());
                found.getChildren().clear();

                ACNode newNode = new ACNode(path.subPath(found.getLevel() + commonLength, path.getLength()),
                        found.getLevel() + commonLength, granted);

                ACNode commonNode = found;
                commonNode.setPath(found.getPath().subPath(0, commonLength));
                commonNode.setGranted(null);

                commonNode.getChildren().put(oldNode.getPath().getNameElement(), oldNode);
                commonNode.getChildren().put(newNode.getPath().getNameElement(), newNode);
           }

        }

        protected HashMap<Element, ACNode> getChildren() {
            return children;
        }

        public ACNode nextNode(Path path) {
            ACNode child = getChild(path);
            if (child == null)
                return null;
            if (!child.subPathMatches(path))
                return null;
            return child;
        }

        public ACNode getChild(Path searchPath) {
            if (searchPath.getLength() <= level + path.getLength())
                return null;
            return children.get(searchPath.getElements()[level + path.getLength()]);
        }

        public boolean hasChildren() {
            return children.size() > 0;
        }

        public boolean subPathMatches(Path testPath) {
            Element[] elements = path.getElements();

            if (path.getLength() > testPath.getLength() - level)
                return false;

            for (int i = 1; (i < path.getLength()) && (i + level < testPath.getLength()); i++) {
                if (!elements[i].equals(testPath.getElements()[i + level])) // level has been checked before in nextNode
                    return false;
            }

            return true;
        }

        public Boolean getGranted() {
            return granted;
        }

        public void setGranted(Boolean granted) {
            this.granted = granted;
        }

        public int getLevel() {
            return level;
        }

        public void setLevel(int level) {
            this.level = level;
        }

        public Path getPath() {
            return path;
        }

        public void setPath(Path path) {
            this.path = path;
        }

    }

    protected boolean permissionGranted(ACNode root, Path path) {
        ACNode node = root;
        while ((node.getGranted() == null || node.getGranted().booleanValue()) &&
                node.hasChildren()) {
            ACNode next = node.nextNode(path);
            if (next == null)
                break;
            node =
                    next;
        }

        if (node.getGranted() == null || node.getGranted().booleanValue())
            return true;
        return false;
    }

    /**
     * {@inheritDoc}
     */
    public boolean canAccess(String workspaceName) throws RepositoryException {
        if (system || wspAccessMgr == null)
            return true;
        return wspAccessMgr.grants(context.getSubject().getPrincipals(), workspaceName);
    }

//-----------------------------------------------< AccessControlManager >---
    /**
     * {@inheritDoc}
     */
    public boolean hasPrivileges(String absPath, Privilege[] privileges) throws PathNotFoundException, RepositoryException {
        checkInitialized();
        // make sure absPath points to an existing node
        checkValidNodePath(absPath);

        if (privileges == null || privileges.length == 0)
            // null or empty privilege array -> return true
            return true;
        else {
            int bits = privilegeRegistry.getBits(privileges);
            if (system)
                // system has always all permissions
                return true;
            else if (anonymous)
                if (bits != PrivilegeRegistry.READ)
                    // anonymous is only granted READ premissions
                    return false;

            // @todo check permission based on principals
            return true;
        }

    }

    /**
     * {@inheritDoc}
     */
    public Privilege[] getPrivileges(String absPath) throws PathNotFoundException, RepositoryException {
        checkInitialized();
        checkValidNodePath(absPath);

        if (anonymous)
            return privilegeRegistry.getPrivileges(PrivilegeRegistry.READ);
        else if (system)
            return privilegeRegistry.getPrivileges(PrivilegeRegistry.ALL);
        else
// @todo check permission based on principals
            return privilegeRegistry.getPrivileges(PrivilegeRegistry.ALL);
    }

    /**
     * {@inheritDoc}
     */
    public AccessControlPolicy[] getEffectivePolicies(String absPath) throws PathNotFoundException, AccessDeniedException, RepositoryException {
        checkInitialized();
        checkPrivileges(absPath, PrivilegeRegistry.READ_AC);

        return new AccessControlPolicy[]{POLICY};
    }

//---------------------------------------< AbstractAccessControlManager >---
    /**
     * @see AbstractAccessControlManager#checkInitialized()
     */
    protected void checkInitialized() throws IllegalStateException {
        if (!initialized)
            throw new IllegalStateException("not initialized");
    }

    /**
     * @see AbstractAccessControlManager#checkPrivileges(String, int)
     */
    protected void checkPrivileges(String absPath, int privileges) throws AccessDeniedException, PathNotFoundException, RepositoryException {
        checkValidNodePath(absPath);
        if (anonymous && privileges != PrivilegeRegistry.READ)
            throw new AccessDeniedException("Anonymous may only READ.");
    }

    /**
     * @see AbstractAccessControlManager#getPrivilegeRegistry()
     */
    protected PrivilegeRegistry getPrivilegeRegistry()
            throws RepositoryException {
        checkInitialized();
        return privilegeRegistry;
    }

    /**
     * @see AbstractAccessControlManager#checkValidNodePath(String)
     */
    protected void checkValidNodePath(String absPath) throws PathNotFoundException, RepositoryException {
        Path path = context.getNamePathResolver().getQPath(absPath);
        if (!path.isAbsolute())
            throw new RepositoryException("Absolute path expected. Found: " + absPath);

        if (context.getHierarchyManager().resolveNodePath(path) == null)
            throw new PathNotFoundException(absPath);
    }
}
